In business software systems, a large amount of data processing resources is spent on processing text. One particularly frequent operation is to substitute some text within a larger text file or document with other text. For example, in a customer list, such an operation could include substituting customer names for customer identification numbers. At a technical level, this can be a very costly operation as actual characters that make up the text have to be shifted in memory in order to make space for replacement characters, or to close gaps if the replacement text is respectively longer or shorter than the text being replaced.
FIG. 1 shows an example of a text replacement operation. For the purpose of this document, a text string of N+1 characters will be referred to as t[0,N]. The subpart of t starting at position i and ending at position k is denoted by t[i,k]. Let t[0,N−1] be the text in which p parts t[m1,n1], . . . , t[mp,np] are to be replaced by text sequences r1, . . . , rp, respectively. Each replacement may be longer or shorter than the part being replaced.
In the example shown, five shaded parts t1[3,4], t1[9,11], t1[16,23], t1[25,26], and t1[29,29] in the text string t1[0,29] are to be replaced. The resultant text string, t2[0,27] will include the five replaced parts shown as t2[3,8], t2[13,14], t2[19,19], t2[21,23], and t2[26,27], respectively. As an example, in order to replace the part t1[3,4] of text t1 with t2[3,8] of text t2, additional space has to be created in text string t1 by moving characters t1[5,29] to the right. Because of this shift, almost all of text t1 will have to be rebuilt to account for changes in length of the replace part, and rebuilt for each replacement step in the operation.
The conventional approach is to save t1 in spare storage, copy the replacements into t1, and restore the intermediate parts of t1 from storage. The conventional method, however, requires N bytes of additional storage and moves up to 2 N bytes, which may be very costly for large texts, or for a large number of such operations.